{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:14:41Z","timestamp":1760217281091,"version":"3.41.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,1,25]],"date-time":"2010-01-25T00:00:00Z","timestamp":1264377600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2010,1,25]]},"DOI":"10.1145\/1711475.1711484","type":"journal-article","created":{"date-parts":[[2010,1,26]],"date-time":"2010-01-26T14:01:38Z","timestamp":1264514498000},"page":"42-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Technical report column"],"prefix":"10.1145","volume":"40","author":[{"given":"Dean","family":"Kelley","sequence":"first","affiliation":[{"name":"Minnesota State University, Mankato"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,1,25]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"\"A Mobile Sensor Network for the Surveillance of Nuclear Materials in Metropolitan Areas \" Jerry Cheng Minge Xie Rong Chen and Fred Roberts 2009-19.  \"A Mobile Sensor Network for the Surveillance of Nuclear Materials in Metropolitan Areas \" Jerry Cheng Minge Xie Rong Chen and Fred Roberts 2009-19."},{"key":"e_1_2_1_2_1","unstructured":"\"Statistics for a Random Network Design Problem \" Fred J. Rispoli and Steven Cosares 2009-20.  \"Statistics for a Random Network Design Problem \" Fred J. Rispoli and Steven Cosares 2009-20."},{"key":"e_1_2_1_3_1","unstructured":"\"Unconditional Lower Bounds against Advice \" Harry Buhrman Lance Fortnow Rahul Santhanam TR09- 064.  \"Unconditional Lower Bounds against Advice \" Harry Buhrman Lance Fortnow Rahul Santhanam TR09- 064."},{"key":"e_1_2_1_4_1","unstructured":"\"Faster exponential time algorithms for the shortest vector problem \" Panagiotis Voulgaris Daniele Micciancio TR09-065.  \"Faster exponential time algorithms for the shortest vector problem \" Panagiotis Voulgaris Daniele Micciancio TR09-065."},{"key":"e_1_2_1_5_1","unstructured":"\"Lower Bounds for Testing Triangle-freeness in Boolean Functions \" Arnab Bhattacharyya Ning Xie TR09- 066.  \"Lower Bounds for Testing Triangle-freeness in Boolean Functions \" Arnab Bhattacharyya Ning Xie TR09- 066."},{"key":"e_1_2_1_6_1","unstructured":"\"On Parity Check (01)-Matrix over Zp \" Hanna Mazzawi Nader Bshouty TR09-067.  \"On Parity Check (01)-Matrix over Zp \" Hanna Mazzawi Nader Bshouty TR09-067."},{"key":"e_1_2_1_7_1","unstructured":"\"Limits on the Social Welfare of Maximal-In-Range Auction Mechanisms \" Dave Buchfuhrer Chris Umans TR09-068.  \"Limits on the Social Welfare of Maximal-In-Range Auction Mechanisms \" Dave Buchfuhrer Chris Umans TR09-068."},{"key":"e_1_2_1_8_1","unstructured":"\"A note on Efremenko's Locally Decodable Codes \" Parikshit Gopalan TR09-069.  \"A note on Efremenko's Locally Decodable Codes \" Parikshit Gopalan TR09-069."},{"key":"e_1_2_1_9_1","unstructured":"\"Pseudorandomness for Width 2 Branching Programs \" Andrej Bogdanov Zeev Dvir Elad Verbin Amir Yehudayoff TR09-070.  \"Pseudorandomness for Width 2 Branching Programs \" Andrej Bogdanov Zeev Dvir Elad Verbin Amir Yehudayoff TR09-070."},{"key":"e_1_2_1_10_1","unstructured":"\"Kolmogorov Complexity in Randomness Extraction \" John Hitchcock A. Pavan N. V. Vinodchandran TR09-071.  \"Kolmogorov Complexity in Randomness Extraction \" John Hitchcock A. Pavan N. V. Vinodchandran TR09-071."},{"key":"e_1_2_1_11_1","unstructured":"\"Hardness Amplification in Proof Complexity \" Paul Beame Trinh Huynh Toniann Pitassi TR09-072.  \"Hardness Amplification in Proof Complexity \" Paul Beame Trinh Huynh Toniann Pitassi TR09-072."},{"key":"e_1_2_1_12_1","unstructured":"\"On Lower Bounds for Constant Width Arithmetic Circuits \" Vikraman Arvind Pushkar Joglekar Srikanth  Srinivasan TR09-073.  \"On Lower Bounds for Constant Width Arithmetic Circuits \" Vikraman Arvind Pushkar Joglekar Srikanth Srinivasan TR09-073."},{"key":"e_1_2_1_13_1","unstructured":"\"A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness \" Suguru Tamaki Yuichi Yoshida TR09-074.  \"A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness \" Suguru Tamaki Yuichi Yoshida TR09-074."},{"key":"e_1_2_1_14_1","unstructured":"\"A Theory of Goal-Oriented Communication \" Oded Goldreich Brendan Juba Madhu Sudan TR09-075.  \"A Theory of Goal-Oriented Communication \" Oded Goldreich Brendan Juba Madhu Sudan TR09-075."},{"key":"e_1_2_1_15_1","unstructured":"\"Improved and Derandomized Approximations for Two-Criteria Metric Traveling Salesman \" Christian Gla\u00dfer Christian Reitwie\u00dfner Maximilian Witek TR09-076.  \"Improved and Derandomized Approximations for Two-Criteria Metric Traveling Salesman \" Christian Gla\u00dfer Christian Reitwie\u00dfner Maximilian Witek TR09-076."},{"key":"e_1_2_1_16_1","unstructured":"\"From Randomness Extraction to Rotating Needles \" Zeev Dvir TR09-077.  \"From Randomness Extraction to Rotating Needles \" Zeev Dvir TR09-077."},{"key":"e_1_2_1_17_1","unstructured":"\"A Probabilistic Inequality with Applications to Threshold Direct-product Theorems \" Falk Unger TR09- 078.  \"A Probabilistic Inequality with Applications to Threshold Direct-product Theorems \" Falk Unger TR09- 078."},{"key":"e_1_2_1_18_1","unstructured":"\"Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation \" Victor Chen Elena Grigorescu Ronald de Wolf TR09-079.  \"Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation \" Victor Chen Elena Grigorescu Ronald de Wolf TR09-079."},{"key":"e_1_2_1_19_1","unstructured":"\"On the Structure of Cubic and Quartic Polynomials \" Elad Haramaty Amir Shpilka TR09-080.  \"On the Structure of Cubic and Quartic Polynomials \" Elad Haramaty Amir Shpilka TR09-080."},{"key":"e_1_2_1_20_1","unstructured":"\"Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes \" Olaf Beyersdorff Zenon Sadowski TR09-081.  \"Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes \" Olaf Beyersdorff Zenon Sadowski TR09-081."},{"key":"e_1_2_1_21_1","unstructured":"\"Characterization of ModL using Prime Modulus \" Vijayaraghavan T.C. TR09-082.  \"Characterization of ModL using Prime Modulus \" Vijayaraghavan T.C. TR09-082."},{"key":"e_1_2_1_22_1","unstructured":"\"Counting Stars and Other Small Subgraphs in Sublinear Time \" Dana Ron Mira Gonen Yuval Shavitt TR09-083.  \"Counting Stars and Other Small Subgraphs in Sublinear Time \" Dana Ron Mira Gonen Yuval Shavitt TR09-083."},{"key":"e_1_2_1_23_1","unstructured":"\"Linear systems over composite moduli \" Arkadev Chattopadhyay Avi Wigderson TR09-084.  \"Linear systems over composite moduli \" Arkadev Chattopadhyay Avi Wigderson TR09-084."},{"key":"e_1_2_1_24_1","unstructured":"\"An Approach to characterize the Regular Languages in TC0 with Linear Wires \" Christoph Behle Andreas Krebs Stephanie Reifferscheid TR09-085.  \"An Approach to characterize the Regular Languages in TC0 with Linear Wires \" Christoph Behle Andreas Krebs Stephanie Reifferscheid TR09-085."},{"key":"e_1_2_1_25_1","unstructured":"\"Optimal testing of Reed-Muller codes \" Arnab Bhattacharyya Swastik Kopparty Grant Schoenebeck Madhu Sudan David Zuckerman TR09-086.  \"Optimal testing of Reed-Muller codes \" Arnab Bhattacharyya Swastik Kopparty Grant Schoenebeck Madhu Sudan David Zuckerman TR09-086."},{"key":"e_1_2_1_26_1","unstructured":"\"Ordered Binary Decision Diagrams Pigeonhole Formulas and Beyond \" Olga Tveretina Carsten Sinz Hans Zantema TR09-087.  \"Ordered Binary Decision Diagrams Pigeonhole Formulas and Beyond \" Olga Tveretina Carsten Sinz Hans Zantema TR09-087."},{"key":"e_1_2_1_27_1","unstructured":"\"Explicit lower bound for fooling polynomials by the sum of small-bias generators \" Shachar Lovett Yoav Tzur TR09-088.  \"Explicit lower bound for fooling polynomials by the sum of small-bias generators \" Shachar Lovett Yoav Tzur TR09-088."},{"key":"e_1_2_1_28_1","unstructured":"\"Are PCPs Inherent in Efficient Arguments?\" Guy Rothblum Salil Vadhan TR09-089.  \"Are PCPs Inherent in Efficient Arguments?\" Guy Rothblum Salil Vadhan TR09-089."},{"key":"e_1_2_1_29_1","unstructured":"\"New Direct-Product Testers and 2-Query PCPs \" Russell Impagliazzo Valentine Kabanets Avi Wigderson TR09-090.  \"New Direct-Product Testers and 2-Query PCPs \" Russell Impagliazzo Valentine Kabanets Avi Wigderson TR09-090."},{"key":"e_1_2_1_30_1","unstructured":"\"On the Matching Problem for Special Graph Classes \" Thanh Minh Hoang TR09-091.  \"On the Matching Problem for Special Graph Classes \" Thanh Minh Hoang TR09-091."},{"key":"e_1_2_1_31_1","unstructured":"\"Proof Systems that Take Advice \" Olaf Beyersdorff Johannes K\u00f6bler Sebastian M\u00fcller TR09-092.  \"Proof Systems that Take Advice \" Olaf Beyersdorff Johannes K\u00f6bler Sebastian M\u00fcller TR09-092."},{"key":"e_1_2_1_32_1","unstructured":"\"Colored Hypergraph Isomorphism is Fixed Parameter Tractable \" Vikraman Arvind Bireswar Das Johannes K\u00f6bler Seinosuke Toda TR09-093.  \"Colored Hypergraph Isomorphism is Fixed Parameter Tractable \" Vikraman Arvind Bireswar Das Johannes K\u00f6bler Seinosuke Toda TR09-093."},{"key":"e_1_2_1_33_1","unstructured":"\"Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs \" Bireswar Das Jacobo Toran Fabian Wagner TR09-094.  \"Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs \" Bireswar Das Jacobo Toran Fabian Wagner TR09-094."},{"key":"e_1_2_1_34_1","unstructured":"\"STRIP EXCHANGING IS HARD \" Swapnoneel Roy TR09-095.  \"STRIP EXCHANGING IS HARD \" Swapnoneel Roy TR09-095."},{"key":"e_1_2_1_35_1","unstructured":"\"A Graph Spectral Approach for Computing Approximate Nash Equilibria \" Haralampos Tsaknakis Paul Spirakis TR09-096.  \"A Graph Spectral Approach for Computing Approximate Nash Equilibria \" Haralampos Tsaknakis Paul Spirakis TR09-096."},{"key":"e_1_2_1_36_1","unstructured":"\"Online Algorithms for Self-Organizing Sequential Search - A Survey \" Rakesh Mohanty N. S. Narayanaswamy TR09-097.  \"Online Algorithms for Self-Organizing Sequential Search - A Survey \" Rakesh Mohanty N. S. Narayanaswamy TR09-097."},{"key":"e_1_2_1_37_1","unstructured":"\"The intersection of two halfspaces has high threshold degree \" Alexander A. Sherstov TR09-098.  \"The intersection of two halfspaces has high threshold degree \" Alexander A. Sherstov TR09-098."},{"key":"e_1_2_1_38_1","unstructured":"\"Improved Inapproximability Results for Maximum k-Colorable Subgraph \" Venkatesan Guruswami Ali Kemal Sinop TR09-099.  \"Improved Inapproximability Results for Maximum k-Colorable Subgraph \" Venkatesan Guruswami Ali Kemal Sinop TR09-099."},{"key":"e_1_2_1_39_1","unstructured":"\"On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution \" Jakob Nordstr\u00f6m Alexander Razborov TR09-100.  \"On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution \" Jakob Nordstr\u00f6m Alexander Razborov TR09-100."},{"key":"e_1_2_1_40_1","unstructured":"\"Progress on Polynomial Identity Testing \" Nitin Saxena TR09-101.  \"Progress on Polynomial Identity Testing \" Nitin Saxena TR09-101."},{"key":"e_1_2_1_41_1","unstructured":"\"Quantum Proofs for Classical Theorems \" Andrew Drucker Ronald de Wolf TR09-102.  \"Quantum Proofs for Classical Theorems \" Andrew Drucker Ronald de Wolf TR09-102."},{"key":"e_1_2_1_42_1","unstructured":"\"On the Hardness of the Noncommutative Determinant \" Vikraman Arvind Srikanth Srinivasan TR09-103.  \"On the Hardness of the Noncommutative Determinant \" Vikraman Arvind Srikanth Srinivasan TR09-103."},{"key":"e_1_2_1_43_1","unstructured":"\"BQP and the Polynomial Hierarchy \" Scott Aaronson TR09-104.  \"BQP and the Polynomial Hierarchy \" Scott Aaronson TR09-104."},{"key":"e_1_2_1_44_1","unstructured":"\"The Remote Point Problem Small Bias Spaces and Expanding Generator Sets \" Vikraman Arvind Srikanth Srinivasan TR09-105.  \"The Remote Point Problem Small Bias Spaces and Expanding Generator Sets \" Vikraman Arvind Srikanth Srinivasan TR09-105."},{"key":"e_1_2_1_45_1","unstructured":"\"Using Elimination Theory to construct Rigid Matrices \" Abhinav Kumar Satyanarayana V. Lokam Vijay M. Patankar Jayalal Sarma TR09-106.  \"Using Elimination Theory to construct Rigid Matrices \" Abhinav Kumar Satyanarayana V. Lokam Vijay M. Patankar Jayalal Sarma TR09-106."},{"key":"e_1_2_1_46_1","unstructured":"\"Improved inapproximability factors for some \u00bf2  p  minimization problems \" Kevin Dick Chris Umans TR09- 107.  \"Improved inapproximability factors for some \u00bf 2 p minimization problems \" Kevin Dick Chris Umans TR09- 107."},{"key":"e_1_2_1_47_1","unstructured":"\"On Generalized Trade-Off Directions for Basic Optimality Principles in Convex and Nonconvex Multiobjective Optimization \" M\u00e4kel\u00e4 Marko M. and Nikulin Yury and Mezei J\u00f3zsef Technical Report Number 940.  \"On Generalized Trade-Off Directions for Basic Optimality Principles in Convex and Nonconvex Multiobjective Optimization \" M\u00e4kel\u00e4 Marko M. and Nikulin Yury and Mezei J\u00f3zsef Technical Report Number 940."},{"key":"e_1_2_1_48_1","unstructured":"\"On Deterministic Two-Way Finite Automata Over a Unary Alphabet \" Kunc Michal and Okhotin Alexander Technical Report Number 950.  \"On Deterministic Two-Way Finite Automata Over a Unary Alphabet \" Kunc Michal and Okhotin Alexander Technical Report Number 950."},{"key":"e_1_2_1_49_1","unstructured":"\"A Study of Unambiguous Finite Automata Over a One-Letter Alphabet \" Okhotin Alexander Technical Report Number 951.  \"A Study of Unambiguous Finite Automata Over a One-Letter Alphabet \" Okhotin Alexander Technical Report Number 951."},{"key":"e_1_2_1_50_1","unstructured":"\"On Equations X + X + C = X + X + D and X + E = F with Unknown X \u00bf N \" Lehtinen Tommi and Okhotin Alexander Technical Report Number 952.  \"On Equations X + X + C = X + X + D and X + E = F with Unknown X \u00bf N \" Lehtinen Tommi and Okhotin Alexander Technical Report Number 952."},{"key":"e_1_2_1_52_1","unstructured":"\"On Equations Over Sets of Integers \" Jez Artur and Okhotin Alexander Technical Report Number 954.  \"On Equations Over Sets of Integers \" Jez Artur and Okhotin Alexander Technical Report Number 954."},{"key":"e_1_2_1_53_1","unstructured":"\"The Shield that Never Was: Societies with Single-Peaked Preferences are More Open to Manipulation and Control \" Faliszewski P. Hemaspaandra L.A. Hemaspaandra E. Rothe J. TR950.  \"The Shield that Never Was: Societies with Single-Peaked Preferences are More Open to Manipulation and Control \" Faliszewski P. Hemaspaandra L.A. Hemaspaandra E. Rothe J. TR950."}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1711475.1711484","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1711475.1711484","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:23:03Z","timestamp":1750249383000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1711475.1711484"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1,25]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,1,25]]}},"alternative-id":["10.1145\/1711475.1711484"],"URL":"https:\/\/doi.org\/10.1145\/1711475.1711484","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2010,1,25]]},"assertion":[{"value":"2010-01-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}