archive-edu.com » EDU » C » COLUMBIA.EDU

Total: 442

Choose link from "Titles, links and description words view":

Or switch to "Titles and links view".
  • Columbia computer scientists presenting four papers at STOC 2015| Dept. of Computer Science, Columbia University
    the computational complexity of other types of games Rocco Servedio Boolean function monotonicity testing requires almost n 1 2 non adaptive queries Xi Chen Columbia University Anindya De IAS Rocco A Servedio Columbia University Li Yang Tan UC Berkeley A natural framework for many types of data sets is to view them as a collection of input output pairs It is often important to know whether a data set is monotone or not in the following sense does increasing the input value always cause the output value to increase Or can it sometimes cause the output to increase and sometimes to decrease The standard way to check a data set for monotonicity is to scan through all the input output pairs However this brute force method is too inefficient for today s massive high dimensional data sets when it is computationally too expensive to make even a single complete pass over the data In some situations it suffices to know only whether a data set is monotone versus far from monotone In this case the key question becomes how many queries are needed to differentiate the two cases The 1998 paper Testing Monotonicity by Oded Goldreich Shafi Goldwasser Eric Lehman and Dana Ron gives an algorithm that requires only n queries for n dimensional datasets with 2 n binary data entries setting an upper bound on the query complexity of testing monotonicity of n variable Boolean functions Subsequent work by Deeparnab Chakrabarty and C Seshadhri recently pushed the number of queries down from n to n 7 8 In the paper Boolean function monotonicity testing requires almost n 1 2 non adaptive queries Xi Chen Anindya De IAS Rocco A Servedio and Li Yang Tan UC Berkeley studied lower bounds on the number of queries required for monotonicity testing Their paper proves a lower bound of n 1 2 c for any positive constant c on the query complexity of two sided error non adaptive algorithms for testing whether an n variable Boolean function is monotone versus far from monotone This bound of n 1 2 is also conjectured to be tight Their result represents an improvement over the previous lower bound of n 1 5 by Chen Servedio and Tan in 2014 Update After this paper was announced a new result by Subhash Khot Dor Minzer and Muli Safra improves the upper bound to n 1 2 as conjectured matching the lower bound of Chen De Servedio and Tan Allison Bishop Indistinguishability Obfuscation for Turing Machines with Unbounded Memory Venkata Koppula University of Texas at Austin Allison Bishop Columbia University Brent Waters University of Texas at Austin Indistinguishability obfuscation is the process of encrypting software so it performs a function without the software itself being intelligible Indistinguishability obfuscation was long thought to be impossible but in 2013 six researchers Sanjam Garg Craig Gentry Shai Halevi Mariana Raykova Amit Sahai Brent Waters published a paper that describes the first plausible candidate indistinguishability obfuscator using a new type of mathematical structure

    Original URL path: http://www.cs.columbia.edu/2015/STOC-2015/ (2016-02-17)
    Open archived version from archive


  • Martha Kim and Shree Nayar among those receiving honors at SEAS Class Day | Dept. of Computer Science, Columbia University
    the recipient of the Edward and Carole Kim Award for Faculty Involvement Established in 2000 by Edward and Carole Kim in appreciation of their son Brian s positive experience at Columbia this award honors a faculty member demonstrating teaching excellence and a special personal commitment to students Nominations are made by undergraduate and graduate students In presenting the award Dean Mary Boyce cited professor Kim s role as a caring professor who actively encouraged undergraduates to participate in her own path breaking research to improve the programmability of hardware accelerators As a result four students became co authors of research papers with Kim an incredible achievement for undergraduate students Shree Nayar Shree Nayar T C Chang Professor of Computer Science received the Distinguished Faculty Teaching Award along with James Hone Mechanical Engineering Instituted by the Columbia Engineering Alumni Association and bestowed on faculty of SEAS since 1996 the award is given on behalf of students and alumni for excellence in teaching including dedication to undergraduate students Selection is based on student evaluations and recommendations of a selection committee made up of three students and two alumni The award was presented by Dr Hitoshi Tanaka in his capacity as president of

    Original URL path: http://www.cs.columbia.edu/2015/Kim-Nayar-receive-SEAS-awards/ (2016-02-17)
    Open archived version from archive

  • Lucas Kowalczyk awarded NSF Graduate Fellowship | Dept. of Computer Science, Columbia University
    three years while giving him the freedom and flexibility to pursue the type of research that interests him I m honored to receive the fellowship and excited that the NSF has offered to support additional work in my research area says Kowalczyk Advised by Tal Malkin and Allison Bishop Lewko Kowalczyk is focusing on functional encryption a new area of cryptography that provides more fine grained control over access to encrypted data Unlike regular encryption today in which a single secret key decrypts all the data functional encryption allows for many different secret keys with different levels of functionality making it possible for some people to see some data and not other data A good application for functional encryption is a medical database that grants doctors access to detailed patient health data while allowing insurance companies to see only whether a procedure was performed or not but nothing else Besides maintaining data privacy functional encryption has other exciting applications including program obfuscation and delegated computation Still there remains much work to be done in order to expand the capabilities of practical functional encryption systems Last year while still an undergraduate he co wrote with Allison Bishop Lewko the paper Bilinear

    Original URL path: http://www.cs.columbia.edu/2015/kowalczyk-NSF-fellowship/ (2016-02-17)
    Open archived version from archive

  • Henrique Teles Maia awarded NSF Graduate Research and GEM Fellowships | Dept. of Computer Science, Columbia University
    34 000 annual stipend and 12 000 cost of education to the graduate institution Maia was one of 2000 students funded out of 16 500 applicants and one of only 40 chosen between applicants based in New York The GEM Fellowship which is intended to increase the number of minority students pursuing doctoral degrees in the natural sciences including computer science likewise covers tuition and provides a living stipend In addition GEM promotes opportunities for individuals to enter industry and arranges paid summer internships for GEM fellows Neither fellowship ties Maia to a particular research path giving him the freedom and flexibility to change his research focus an important consideration since Maia has yet to begin his graduate studies and is interested in computational mechanics which models the dynamics of physical objects and has applications in both engineering and computer graphics He has a great start As an undergraduate already pursuing research as part of the Columbia Computer Graphics Group Maia has been studying in particular contact mechanics which concerns the principled treatment of interactions that occur on surfaces of bodies that collide or are in contact with one another Maia is working to develop new methods to compute friction

    Original URL path: http://www.cs.columbia.edu/2015/maia-NSF-GEM-fellowships/ (2016-02-17)
    Open archived version from archive

  • About Steve Bellovin's Pseudo-Random Blog
    2015 October 2015 July 2015 June 2015 May 2015 April 2015 March 2015 February 2015 January 2015 December 2014 November 2014 September 2014 July 2014 June 2014 May 2014 April 2014 February 2014 December 2013 October 2013 August 2013 July 2013 May 2013 August 2012 June 2012 May 2012 April 2012 February 2012 January 2012 December 2011 November 2011 October 2011 July 2011 June 2011 May 2011 April 2011 March 2011 November 2010 October 2010 September 2010 August 2010 July 2010 June 2010 January 2010 December 2009 November 2009 September 2009 August 2009 July 2009 April 2009 March 2009 February 2009 January 2009 December 2008 November 2008 September 2008 August 2008 July 2008 June 2008 April 2008 March 2008 February 2008 January 2008 December 2007 November 2007 October 2007 September 2007 August 2007 July 2007 June 2007 I m Steve Bellovin my login is smb hence the name of this blog and I m a professor of computer science My primary research focus is computer and Internet security but I have a strong interest in privacy and related issues Follow the link at the side for more details about me This blog is non traditional in one important way it has no provision for reader comments It s not that I don t care about what people say it s that I don t know how to do it securely That is I don t know that existing blog software is secure and for a security specialist failures are especially embarrassing Beyond that I don t know any good ways to deal with blog spam at least not without using more possibly insecure code and worse yet collecting things like email addresses I may revisit this decision later let me know what you think So what blogging software am I

    Original URL path: https://www.cs.columbia.edu/~smb/blog/control/blog.html (2016-02-17)
    Open archived version from archive

  • SMBlog -- 1 February 2016
    December 2007 November 2007 October 2007 September 2007 August 2007 July 2007 June 2007 Caveats About Computer Science For All 1 February 2016 As someone who learned to program at age 14 and who benefited immensely from the opporunities my high school s computer provided I think that it s a great idea to give more children a similar chance Programming was more fun than just about anything else I d ever done and it quickly displaced math physics and law as possible career paths for me No I probably would never have become a lawyer since math and science were too much fun but I was interested in law and policy even then And yes quite obviously my career path was shaped by that early opportunity Given all that I m delighted by the White House s Computer Science For All initiative Even people who don t become programmers probably the large majority of students who will take these classes will benefit from that sort of thinking That said I do have a few concerns Teaching the teachers The White House recognizes that we need far more people qualified to teach computer science It s a crucial need but I wonder if 4 billion is nearly enough money I wonder if we need another level teaching the teachers who will teach the children s teachers The teachers have to really understand programming I had another spot of luck when I was young I had a relative who know how to program and who could answer my questions My career almost died aborning there were two or three crucial ideas that I just didn t get at first I don t know if I d have been able to work past them on my own Reteaching the teachers Computer science is incredibly dynamic even at the introductory levels Let s put it like this the iPhone is less than 10 years old but it s completely changed the industry Teaching children to program but ignoring smart phones would be a bad idea if only because they ll be less interested in the subject matter But progress isn t stopping with smart phones not very many years from now school kids will want need to learn about programming the next big thing whatever it will be Internet of Things Wearables Programmable drones I have no idea but I m sure it will happen In other words the teachers are going to need frequent refreshers The curriculum will also need frequent updates There is in service training today but I suspect there will need to be more In most subjects the content of the course doesn t change drastically every five years in computer science it does Yes programming is programing But the details of what you program will change In other words the the training budget has to be an ongoing commitment Even if 4 billion is the right number now more will be needed not very many years in the

    Original URL path: https://www.cs.columbia.edu/~smb/blog/2016-02/2016-02-01.html (2016-02-17)
    Open archived version from archive

  • SMBlog -- 3 January 2016
    2009 February 2009 January 2009 December 2008 November 2008 September 2008 August 2008 July 2008 June 2008 April 2008 March 2008 February 2008 January 2008 December 2007 November 2007 October 2007 September 2007 August 2007 July 2007 June 2007 Why More Effort Won t Solve the Exceptional Access Problem 3 January 2016 In the debate over government exceptional access to encrypted communications opponents with a technical bent and that includes me have said that it won t work that such a scheme would inevitably lead to security problems The response from the policy side not from techncial folk has been to assert that perhaps more effort would suffice FBI Director James Comey has said But my reaction to that is I m not sure they ve really tried Hillary Clinton wants a Manhattan like project something that would bring the government and the tech communities together More effort won t solve the problem but the misunderstanding lies at the heart of why exceptional access is so hard The Manhattan Project had to solve one problem It was a very hard problem one they didn t even know could be solved but it was just one problem Exceptional access is a separate problem for every app every service every device Possibly a few will get it right More likely they ll fail even more abysmally than they ve failed at even simple encryption Study Developers have botched encryption in seven out of eight Android apps and 80 percent of iOS apps after study 10 327 out of 11 748 applications that use cryptographic APIs 88 overall make at least one mistake after study root causes are not simply careless developers but also limitations and issues of the current SSL development paradigm after study We demonstrate that SSL certificate validation is completely

    Original URL path: https://www.cs.columbia.edu/~smb/blog/2016-01/2016-01-03.html (2016-02-17)
    Open archived version from archive

  • SMBlog -- 22 December 2015
    real world that sort of mutual trust is hard to come by but that s a post for another day too Alice starts by sending a message to Bob A B Na A Kb In English this says I Alice am sending my name and a nonce Na those are encrypted with Bob s public key Kb and no one else can read or tamper with that part of the message After this message is sent and received both Alice and Bob know that Alice wants to talk to Bob and that she has sent Na Eve knows who wants to talk to whom but doesn t know Na The next message from Bob to Alice is a bit more subtle B A Na Nb Ka Bob has returned Alice s nonce to her generated his own nonce Nb and encrypted both with Alice s key Ka Why does Bob send Alice s nonce back to her It serves two different purposes First it assures freshness this is a response to Alice s message from this session not from some other run of the protocol It s not an old message that Eve has saved up to confuse things At least as important it shows that the message really came from Bob Na was sent encrypted to Bob so no one else could have read it In other words Alice now knows that despite Eve s best efforts her message got through to Bob and Bob got his reply through to Alice Recall that if Eve tampered with an encrypted message it wouldn t decrypt properly which Alice would have noticed At this point both Alice and Bob know Na and Nb Eve knows neither In the third and last message Alice returns Bob s nonce to him A B Nb Kb This proves that Alice received message 2 correctly otherwise she wouldn t know Nb At the end of this protocol Alice and Bob each know both nonces more important both know that the other party knows both nonces They also know who the other party is only Bob can read messages encrypted with Kb and only Alice can read messages encrypted with Ka They can then use those nonces to generate a session key I won t go into how that s done but today that isn t that hard Problem solved right There are two values that they and only they know The point here is that encryption even in a simple scenario isn t that simple You really need a session key setting that up properly takes several messages and things like nonces This isn t even a realistic scenario where does Alice s private key come from Her password is the obvious answer but she doesn t want to type it constantly For a more realistic design that is one more usable in the real world see this dialog about the design of the Kerberos system It s not easy going but it s probably

    Original URL path: https://www.cs.columbia.edu/~smb/blog/2015-12/2015-12-22.html (2016-02-17)
    Open archived version from archive