Recent Paper Claiming NP = PSpace. Any thoughts? Computer Science |
- Recent Paper Claiming NP = PSpace. Any thoughts?
- What lessons has coding taught you about problem solving?
- python/placements/datascience/analysis/beginner
- Most space-efficient way of storing pool table state
- Executable data flow analysis for privacy enforcement
- How would fundamental computer science courses help me?
- Most user-friendly way to input 200 bits of data?
- Socket API - socket() and open()
| Recent Paper Claiming NP = PSpace. Any thoughts? Posted: 27 Jul 2019 12:54 PM PDT A few days ago I came across the following paper on ArXiv, claiming to prove NP = PSpace and that NP = CoNP. I am curious if any experts frequent this subreddit and have opinions on the approach taken or about whether or not the result seems sound. Proofs of statements like this in complexity theory are notoriously difficult, and there is a long history of failed attempts at similar questions like P =? NP. Proof compression and NP versus PSPACE. Part 2 The author, Lev Gordeev, is a professor at the University of Tubingen in Germany and has numerous publications going back decades. (I mention this only because there are a lot of people who come out of nowhere claiming to prove things like this and they are pretty much always ridiculous. The author is clearly not one of these people.) [link] [comments]  |
| What lessons has coding taught you about problem solving? Posted: 27 Jul 2019 08:43 PM PDT Non-developer/programmer here, but very curious as to what lessons coding has taught you about problem solving, and what lessons non-programmers could learn from programmers about problem solving? [link] [comments]  |
| python/placements/datascience/analysis/beginner Posted: 27 Jul 2019 11:02 PM PDT I am in a 3rd yr CSE undergrad, and I am learning python So I have a question that .py is a good lang for placements, I am interested in data science and analysis too. I wanna know the step by step process? Anyone? [link] [comments]  |
| Most space-efficient way of storing pool table state Posted: 27 Jul 2019 04:29 PM PDT Hi, I want to serialize the position of a set of pool balls on a pool table. Let's say each ball's XY position can be accurately represented as ints from 0-1000. There are 16 balls to record divided into four types: 7 spots, 7 stripes, one cue ball and one 8-ball (ignoring which specific spot or stripe number it was) So a first approach might be to list spots first, then stripes, then cue, then 8. Each ball needs 10 bits per position axis, so the total storage requirement is 16 x (10 + 10) = 320 bits. Can I do better? Was thinking of representing the 2D space as a 1D line that scans left-right top-bottom across the table, then each ball's coord is a single number that is the distance from the previous one. [link] [comments]  |
| Executable data flow analysis for privacy enforcement Posted: 27 Jul 2019 06:10 PM PDT I have been thinking about this idea for some time, maybe you will find it viable and push it forward. I'm not currently able to work on it myself, because I'm busy with other projects of mine. The idea is to analyze machine code of programs to enforce user privacy rights. I think it's possible to prevent data leaks or data theft. Most of the data that is stolen - is send through the network. The packet data that the program fills in the memory is always based on some other data, possibly including user's private data. I think it is possible to track the source of the data by analyzing machine code of executables. That is, each instruction that writes to memory requires a source operand, be it an immediate value or another memory address (excluding those few writing predefined data). If one wants to steal the private data, one must load it into memory, process it and then send through the network. Having identified memory region of private data, it should be possible to track the data flow in the instructions, between confidential memory regions and between network syscalls. Even if the adversary wants to only identify/track users without stealing raw data, it should still be possible to detect and prevent it. For instance, creating a cryptographic hash value based on user data, or encrypting the data, would still reveal the connection in machine code. That is, even if we would see encrypted, random looking stream at the network interface, we would be able to determine if those bytes are based on our private data or not. When done right at the OS level, this could be a revolutionary countermeasure against data theft. Users would be able to explicitly allow/deny access of their data, per application basis. All of this should be possible without changing any software development patterns. It should also be possible to identify stealing of sensor data, such as data coming from microphones, video streams, etc. I don't know if this is new idea or not, but I want to share it anyway - maybe someone will take good care of it. Please tell if this is a known topic. Or if you know papers raising this topic. Thank you. [link] [comments]  |
| How would fundamental computer science courses help me? Posted: 27 Jul 2019 05:41 AM PDT As someone who is working in ML and having entered it through the non traditional route (undergraduate in economics with a major in econometrics), I have been advised by a lot of my peers to do a introductory computer science course such as CS50 by Harvard on EdX. I have asked them why do they think it would be helpful and they mention data structures and algorithms etc.. and how their knowledge would help while interviewing. I am aware of the tough questions asked around them especially at large tech companies, however I do not see the benefit of data structures and algorithms and other such core concepts in my day to day work. I would eventually want to move to a more software development role but I fail to see how would such concepts help me. Can somebody please shed some more light on this and how these courses would be relevant to me? [link] [comments]  |
| Most user-friendly way to input 200 bits of data? Posted: 27 Jul 2019 11:18 AM PDT My phone app needs a user to provide around 200 bits' worth of data. The only direct data entry mechanism available is user screen touch events, so no direct access to network, camera, filesystem etc. However, you CAN access the image library for an image containing a visual representation of the data. You can't read the pixel data but you can show it on screen to assist the user. So the following would be valid solutions: - have the user type a 60-digit decimal number (the user either knows the number, or can be shown the number from an image containing it) - have the user enter a series of english words that can be decoded to reconstruct the data bits (again an image with the words written on it can be shown) - display a 14x14 checkerboard pattern and have the user tap on all the black squares => 196 bits of data - draw a squiggly line of some kind and have the user trace it with their finger What's the fastest and most user friendly method you can think of? Edit: adding part of my reply from below for more clarity on the exact problem: I am trying to write a filter (AKA "lens") for Snapchat using their Lens Studio product. I want a way for a user to serialize some state about the lens and send it to a friend, who can then configure their lens with the same state. There is essentially no means for the user to get data into a running lens, other than tapping the screen, or selecting an image from the phone's image library (and the image pixel data is not readable in any way in the lens sandbox; it can only be rendered to the screen). So a lens cannot get its data from an image directly, but can show the image on the screen as a way to instruct the user to tap in the data somehow. I estimate the data needed can be stored in 200 bits or less. [link] [comments]  |
| Socket API - socket() and open() Posted: 27 Jul 2019 01:17 PM PDT When I call SOCKET() as an API call, I know it creates a file descriptor, and returns an object for operating over that file descriptor using other API calls such as BIND(), LISTEN(), CONNECT(), and allocates system resources. What I don't know: is this API using I/O system calls to read, write, and open the device file attached to the processing layers on my network interface hardware? In other words, since everything in Linux is a file, is the API call SOCKET(), really the system call OPEN(<path_to_device_file>)? Bonus: are these other API calls abstractions that translate down to the read/write system calls that operate on the file descriptor and eventually the device file? Thanks. [link] [comments]  |
| You are subscribed to email updates from Computer Science: Theory and Application. To stop receiving these emails, you may unsubscribe now. | Email delivery powered by Google |
| Google, 1600 Amphitheatre Parkway, Mountain View, CA 94043, United States | |
No comments:
Post a Comment