Search results for "Reductions"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
135	Eljas Soisalon-Soininen	Elimination of Single Productions from LR Parsers in Conjunction with the Use of Default Reductions.	POPL	1977	DBLP DOI BibTeX RDF
116	Lane A. Hemaspaandra, Mayur Thakur	Query-Monotonic Turing Reductions.	COCOON	2005	DBLP DOI BibTeX RDF
103	Shih-Wei Liao	Parallelizing User-Defined and Implicit Reductions Globally on Multiprocessors.	Asia-Pacific Computer Systems Architecture Conference	2006	DBLP DOI BibTeX RDF	reduction recognition, implicit reductions, user-defined reductions, parallelization, multiprocessor, multicore, Reduction, data flow analysis, interprocedural analysis
84	Arfst Nickelsen, Till Tantau	Closure of Polynomial Time Partial Information Classes under Polynomial Time Reductions.	FCT	2001	DBLP DOI BibTeX RDF	polynomial time reductions, verboseness, p-selectivity, positive reductions, structural complexity, partial information
74	Anuj Dawar, Yuguo He	Parameterized Complexity Classes under Logical Reductions.	MFCS	2009	DBLP DOI BibTeX RDF
67	Dan Gutfreund, Salil P. Vadhan	Limitations of Hardness vs. Randomness under Uniform Reductions.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF	derandomization, pseudorandom generators, black-box reductions
62	Degang Chen 0002	The Part Reductions in Information Systems.	Rough Sets and Current Trends in Computing	2004	DBLP DOI BibTeX RDF
61	Steven J. Deitz, David Callahan, Bradford L. Chamberlain, Lawrence Snyder	Global-view abstractions for user-defined reductions and scans.	PPoPP	2006	DBLP DOI BibTeX RDF	Chapel, parallel programming, MPI, reductions, scans, parallel prefix
61	Edmund M. Clarke, Somesh Jha, Wilfredo R. Marrero	Partial Order Reductions for Security Protocol Verification.	TACAS	2000	DBLP DOI BibTeX RDF	partial order reductions and security, Model checking
61	Salvador Lucas	Needed Reductions with Context-Sensitive Rewriting.	ALP/HOA	1997	DBLP DOI BibTeX RDF	needed reductions, replacement restrictions, functional programming, strategies, term rewriting systems
56	John M. Hitchcock, Aduri Pavan	Comparing Reductions to NP-Complete Sets.	ICALP (1)	2006	DBLP DOI BibTeX RDF
56	Jin-yi Cai, Lane A. Hemaspaandra, Gerd Wechsung	Robust Reductions.	COCOON	1998	DBLP DOI BibTeX RDF
55	Steven J. Deitz, Bradford L. Chamberlain, Lawrence Snyder	High-level Language Support for User-defined Reductions.	J. Supercomput.	2002	DBLP DOI BibTeX RDF	user-defined reductions, parallel programming, scientific computing, high-level languages
50	Frédéric Lang, Radu Mateescu 0001	Partial Order Reductions Using Compositional Confluence Detection.	FM	2009	DBLP DOI BibTeX RDF
50	Xavier Redon, Paul Feautrier	Scheduling reductions.	International Conference on Supercomputing	1994	DBLP DOI BibTeX RDF
50	Lane A. Hemachandra, Sanjay Jain 0001	On the Limitations of Locally Robust Positive Reductions.	FSTTCS	1989	DBLP DOI BibTeX RDF
49	Radu Iosif	Symmetry reductions for model checking of concurrent dynamic software.	Int. J. Softw. Tools Technol. Transf.	2004	DBLP DOI BibTeX RDF	Orbit problem, Temporal logic, Software verification, Symmetry reductions
49	Ahto Buldas, Sven Laur, Margus Niitsoo	Oracle Separation in the Non-uniform Model.	ProvSec	2009	DBLP DOI BibTeX RDF
48	Yan-Cheng Chang, Chun-Yuan Hsiao, Chi-Jen Lu	The Impossibility of Basing One-Way Permutations on Central Cryptographic Primitives.	J. Cryptol.	2006	DBLP DOI BibTeX RDF	Private information retrieval, Cryptographic primitives, Black-box reductions, Trapdoor functions, One-way permutations
47	Helena Handschuh, Yiannis Tsiounis, Moti Yung	Decision Oracles are Equivalent to Matching Oracles.	Public Key Cryptography	1999	DBLP DOI BibTeX RDF	Diffie-Hellman variants, randomized reductions, uniform reductions, homomorphic encryption functions (ElGamal, Goldwasser-Micali, Okamoto-Uchiyama, Naccache-Stern), random self-reducibility, universal malleability, public-key encryption, decision problems, matching problems
44	Ahto Buldas, Aivo Jürgenson, Margus Niitsoo	Efficiency Bounds for Adversary Constructions in Black-Box Reductions.	ACISP	2009	DBLP DOI BibTeX RDF
44	Gary M. Zoppetti, Gagan Agrawal, Rishi Kumar	Compiler and Runtime Support for Irregular Reductions on a Multithreaded Architecture.	IPDPS	2002	DBLP DOI BibTeX RDF
44	Jesús Corbal, Roger Espasa, Mateo Valero	On the Efficiency of Reductions in µ-SIMD Media Extensions.	IEEE PACT	2001	DBLP DOI BibTeX RDF
44	Gary M. Zoppetti, Gagan Agrawal, Rishi Kumar	Impact of Data Distribution on Performance of Irregular Reductions on Multithreaded Architectures.	HPCN	2001	DBLP DOI BibTeX RDF
44	Arnaud Durand 0001, Miki Hermann, Phokion G. Kolaitis	Subtractive Reductions and Complete Problems for Counting Complexity Classes.	MFCS	2000	DBLP DOI BibTeX RDF
44	Vikraman Arvind, Yenjo Han, Lane A. Hemachandra, Johannes Köbler, Antoni Lozano, Martin Mundhenk, Mitsunori Ogiwara, Uwe Schöning, Riccardo Silvestri, Thomas Thierauf	Reductions to Sets of Low Information Content.	ICALP	1992	DBLP DOI BibTeX RDF
43	Jay Belanger, Aduri Pavan, Jie Wang 0002	Reductions Do Not Preserve Fast Convergence Rates in Average Time.	Algorithmica	1999	DBLP DOI BibTeX RDF	Average polynomial time, Distributional problem, Reductions
43	Jack H. Lutz, Yong Zhao	The Density of Weakly Complete Problems under Adaptive Reductions.	CCC	1997	DBLP DOI BibTeX RDF	dense languages, polynomial reductions, sparse languages, weak completeness, computational complexity, complexity classes, resource-bounded measure
43	Helmut Veith	Succinct Representation, Leaf Languages, and Projection Reductions.	CCC	1996	DBLP DOI BibTeX RDF	leaf languages, quantifier-free reductions, computational complexity, descriptive complexity, succinct representation
43	Richard Kennaway, Jan Willem Klop, M. Ronan Sleep, Fer-Jan de Vries	Transfinite Reductions in Orthogonal Term Rewriting Systems (Extended Abstract).	RTA	1991	DBLP DOI BibTeX RDF	orthogonal term rewriting systems, infinitary rewriting, strong converging reductions, infinite Church-Rosser Properties, Böhm Trees, head normal forms, non-unifiable term rewriting systems, normal forms
43	Richard Beigel, Bin Fu	Circuits Over PP and PL.	CCC	1997	DBLP DOI BibTeX RDF	reduction, oracle, circuit, closure, PL, Boolean formula, AC, NC, PP
43	Mark E. Stickel	A Case Study of Theorem Proving by the Knuth-Bendix Method: Discovering That x³=x Implies Ring Commutativity.	CADE	1984	DBLP DOI BibTeX RDF
42	Manindra Agrawal	Pseudo-Random Generators and Structure of Complete Degrees.	CCC	2002	DBLP DOI BibTeX RDF	Completeness, Reductions, Pseudo-random Generators
41	Ashish V. Naik, Alan L. Selman	A Note on P-selective sets and on Adaptive versus Nonadaptive Queries to NP.	CCC	1996	DBLP DOI BibTeX RDF	P, p-selective, adaptive reductions, nonadaptive reductions, complexity classes, NP
37	Daniele Micciancio	Efficient reductions among lattice problems.	SODA	2008	DBLP BibTeX RDF
37	Christophe Pajault, Jean-François Pradat-Peyre, Pierre Rousseau	Adapting Petri Nets Reductions to Promela Specifications.	FORTE	2008	DBLP DOI BibTeX RDF
37	Christian Glaßer, Alan L. Selman, Samik Sengupta	Reductions between Disjoint NP-Pairs.	CCC	2004	DBLP DOI BibTeX RDF
37	A. Prasad Sistla	Symmetry Reductions in Model-Checking.	VMCAI	2003	DBLP DOI BibTeX RDF
37	Jan-Jan Wu	An Interleaving Transformation for Parallelizing Reductions for Distributed-Memory Parallel Machines.	J. Supercomput.	2000	DBLP DOI BibTeX RDF	triangular systems solver, parallel processing, program transformation, reduction, parallelizing compilation, distributed-memory
37	Tatsuaki Okamoto, Shigenori Uchiyama	Security of an Identity-Based Cryptosystem and the Related Reductions.	EUROCRYPT	1998	DBLP DOI BibTeX RDF
37	Jin-yi Cai, Ashish V. Naik, D. Sivakumar	On the Existence of Hard Sparse Sets under Weak Reductions.	STACS	1996	DBLP DOI BibTeX RDF
37	Vincent Danos, Marco Pedicini, Laurent Regnier	Directed Virtual Reductions.	CSL	1996	DBLP DOI BibTeX RDF
37	Andreas Blass, Yuri Gurevich	Randomizing Reductions of Search Problems.	FSTTCS	1991	DBLP DOI BibTeX RDF
37	Lefteris M. Kirousis, Paul G. Spirakis	Probabilistic Log-Space Reductions and Problems Probabilistically Hard for P.	SWAT	1988	DBLP DOI BibTeX RDF
37	Eladio Gutiérrez, Oscar G. Plata, Emilio L. Zapata	On Improving the Performance of Data Partitioning Oriented Parallel Irregular Reductions.	PDP	2002	DBLP DOI BibTeX RDF	Irregular reductions, shared-memory multiprocessor, data locality, workload balancing
36	Marisa Venturini Zilli	Cofinality in Reduction Graphs.	CAAP	1983	DBLP DOI BibTeX RDF
36	Adi Akavia, Oded Goldreich 0001, Shafi Goldwasser, Dana Moshkovitz	On basing one-way functions on NP-hardness.	STOC	2006	DBLP DOI BibTeX RDF	adaptive versus non-adaptive machines, reductions, one-way functions, interactive proof systems, average-case complexity
35	Mitsunori Ogihara	Sparse P-Hard Sets Yield Space-Efficient Algorithms.	FOCS	1995	DBLP DOI BibTeX RDF	sparse P-hard sets, space-efficient algorithms, logspace many-one reductions, poly-logarithmic space-computable many-one reductions, computational complexity
35	Stavros S. Cosmadakis	Logical Reducibility and Monadic NP	FOCS	1993	DBLP DOI BibTeX RDF	syntactically restricted first-order reductions, logical reducibility, monadic NP, polynomial-time many-one reductions, directed reachability, encodings, first-order logic, NP-complete problems, relational structures
31	Ulrich Flegel, Joachim Biskup	Requirements of Information Reductions for Cooperating Intrusion Detection Agents.	ETRICS	2006	DBLP DOI BibTeX RDF
31	Wenjing Rao, Alex Orailoglu, George Su	Frugal linear network-based test decompression for drastic test cost reductions.	ICCAD	2004	DBLP DOI BibTeX RDF
31	Edmund M. Clarke, Somesh Jha, Wilfredo R. Marrero	Efficient verification of security protocols using partial-order reductions.	Int. J. Softw. Tools Technol. Transf.	2003	DBLP DOI BibTeX RDF	Model checking, Security protocols, Partial-order reduction
31	Matthew B. Dwyer, Robby, Xianghua Deng, John Hatcliff	Space Reductions for Model Checking Quasi-Cyclic Systems.	EMSOFT	2003	DBLP DOI BibTeX RDF
31	Ruoming Jin, Gagan Agrawal	Performance prediction for random write reductions: a case study in modeling shared memory programs.	SIGMETRICS	2002	DBLP DOI BibTeX RDF
31	Gautam Gupta, Sanjay V. Rajopadhye, Patrice Quinton	Scheduling reductions on realistic machines.	SPAA	2002	DBLP DOI BibTeX RDF	parametric integer programming, dependence analysis, automatic parallelization, scheduling theory, polyhedral model, affine recurrence equations
31	Simon St. James, Ulrich Ultes-Nitsche	Computing property-preserving behaviour abstractions from trace reductions: abstraction-based verification of linear-time properties under fairness.	PODC	2001	DBLP DOI BibTeX RDF	behaviour abstraction, satisfaction within fairness, weakly continuation-closed homomorphisms, partial-order methods, trace reduction
31	Peter Niebert, Michaela Huhn, Sarah Zennou, Denis Lugiez	Local First Search - A New Paradigm for Partial Order Reductions.	CONCUR	2001	DBLP DOI BibTeX RDF
31	Vikraman Arvind, Johannes Köbler, Martin Mundhenk	On Bounded Truth-Table, Conjunctive, and Randomized Reductions to Sparse Sets.	FSTTCS	1992	DBLP DOI BibTeX RDF
31	Alfred Strey	On the Efficient Implementation of Reductions on the Cell Broadband Engine.	PDP	2010	DBLP DOI BibTeX RDF	Reductions, Cell Broadband Engine
31	Maria-Florina Balcan, Nikhil Bansal 0001, Alina Beygelzimer, Don Coppersmith, John Langford 0001, Gregory B. Sorkin	Robust reductions from ranking to classification.	Mach. Learn.	2008	DBLP DOI BibTeX RDF	Classification, Ranking, Reductions
31	Pierluigi Crescenzi	A Short Guide to Approximation Preserving Reductions.	CCC	1997	DBLP DOI BibTeX RDF	approximation preserving reductions, computational complexity, complexity, combinatorial optimization
30	Serge Gaspers, Gregory B. Sorkin	A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between.	SODA	2009	DBLP DOI BibTeX RDF
30	Bin Zhou, Yizheng Ye, Zhao-lin Li, Xin-chun Wu, Rui Ke	A new low power test pattern generator using a variable-length ring counter.	ISQED	2009	DBLP DOI BibTeX RDF
30	Alex K. Simpson	Reduction in a Linear Lambda-Calculus with Applications to Operational Semantics.	RTA	2005	DBLP DOI BibTeX RDF
30	John M. Hitchcock	Small Spans in Scaled Dimension.	CCC	2004	DBLP DOI BibTeX RDF
30	Yan-Cheng Chang, Chun-Yun Hsiao, Chi-Jen Lu	On the Impossibilities of Basing One-Way Permutations on Central Cryptographic Primitives.	ASIACRYPT	2002	DBLP DOI BibTeX RDF
30	Emma Enström, Viggo Kann	Computer lab work on theory.	ITiCSE	2010	DBLP DOI BibTeX RDF	computer lab work, learning theoretical computer science, reductions
30	Marcio K. Oikawa, João Eduardo Ferreira, Simon Malkowski, Calton Pu	Towards Algorithmic Generation of Business Processes: From Business Step Dependencies to Process Algebra Expressions.	BPM	2009	DBLP DOI BibTeX RDF	series-parallel reductions and process algebra, business process modeling, directed acyclic graphs
30	Chris Peikert, Alon Rosen	Lattices that admit logarithmic worst-case to average-case connection factors.	STOC	2007	DBLP DOI BibTeX RDF	algebraic number theory, worst-case to average-case reductions, lattices
30	Jin-yi Cai, Hong Zhu 0004	Progress in Computational Complexity Theory.	J. Comput. Sci. Technol.	2005	DBLP DOI BibTeX RDF	computational complexity theory, PCP theorem, logspace complexity, Reingold's theorem, GAP problem, complexity of lattice problems, worst-case to average-case reductions, extractors, pseudorandomness, inapproximability, primality testing, theoretical computer science, holographic algorithms
30	John H. Reif	Fast Spatial Decomposition and Closest Pair Computation for Limited Precision Input.	Algorithmica	2000	DBLP DOI BibTeX RDF	Visibility problems, Gap-preserving reductions, Telecommunications, Terrains, Inapproximability, Art gallery
30	James C. Corbett	Using shape analysis to reduce finite-state models of concurrent Java programs.	ACM Trans. Softw. Eng. Methodol.	2000	DBLP DOI BibTeX RDF	Java, modeling, shape analysis, concurrent systems, state-space reductions, finite-state verification, model extraction
26	Damian Kurpiewski, Witold Pazderski, Wojciech Jamroga, Yan Kim	STV+Reductions: Towards Practical Verification of Strategic Ability Using Model Reductions.	CoRR	2023	DBLP DOI BibTeX RDF
26	Benjamin Y. Chan, Cody Freitag, Rafael Pass	Universal Reductions: Reductions Relative to Stateful Oracles.	TCC (3)	2022	DBLP DOI BibTeX RDF
26	Damian Kurpiewski, Witold Pazderski, Wojciech Jamroga, Yan Kim	STV+Reductions: Towards Practical Verification of Strategic Ability Using Model Reductions. (PDF / PS)	AAMAS	2021	DBLP BibTeX RDF
26	Louis Vuilleumier	Continuous reductions on the Scott domain and decomposability conjecture. (Réductions continues sur le domaine de Scott et conjecture de la décomposabilité).		2021	RDF
26	Luc Pellissier	Reductions and linear approximations. (Réductions et approximations linéaires).		2017	RDF
26	Luoshan Xu, Jing Zhao	Reductions and Saturation Reductions of (Abstract) Knowledge Bases.	ISDT	2013	DBLP DOI BibTeX RDF
26	Rakesh M. Verma	Complexity of Normal Form Properties and Reductions for Term Rewriting Problems Complexity of Normal Form Properties and Reductions for Term Rewriting Problems.	Fundam. Informaticae	2009	DBLP DOI BibTeX RDF
26	Lionel Marie-Magdeleine	Sous-typage coercitif en présence de réductions non-standards dans un système aux types dépendants. (Coercive subtyping in a system with dependents types and non-standards reductions).		2009	RDF
26	Ming-Hong Lai, Chia-Chi Chu, Wu-Shiung Feng	On the Equivalent of Structure Preserving Reductions Approach and Adjoint Networks Approach for VLSI Interconnect Reductions.	IEICE Trans. Fundam. Electron. Commun. Comput. Sci.	2007	DBLP DOI BibTeX RDF
26	Paul Young	How reductions to sparse sets collapse the polynomial-time hierarchy: a primer: Part II restricted polynomial-time reductions.	SIGACT News	1992	DBLP DOI BibTeX RDF
26	Paul Young	How reductions to sparse sets collapse the polynomial-time hierarchy: a primer; part I: polynomial-time Turing reductions.	SIGACT News	1992	DBLP DOI BibTeX RDF
26	J. Roger Hindley	Combinatory Reductions and Lambda Reductions Compared.	Math. Log. Q.	1977	DBLP DOI BibTeX RDF
25	Chi-Jen Lu	On the Security Loss in Cryptographic Reductions.	EUROCRYPT	2009	DBLP DOI BibTeX RDF
25	Michael Kowalczyk	Classification of a Class of Counting Problems Using Holographic Reductions.	COCOON	2009	DBLP DOI BibTeX RDF	Fibonacci gates, holographic reduction, interpolation, holographic algorithms
25	Jin-yi Cai, Pinyan Lu, Mingji Xia	Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness.	FOCS	2008	DBLP DOI BibTeX RDF
25	Dorothea Baumeister, Jörg Rothe	The Three-Color and Two-Color TantrixTM Rotation Puzzle Problems Are NP-Complete Via Parsimonious Reductions.	LATA	2008	DBLP DOI BibTeX RDF
25	Sanjam Garg, Raghav Bhaskar, Satyanarayana V. Lokam	Improved Bounds on Security Reductions for Discrete Log Based Signatures.	CRYPTO	2008	DBLP DOI BibTeX RDF	Schnorr Signature Scheme, Provable Security, Random Oracle Model
25	Abdullah Konak	Combining network reductions and simulation to estimate network reliability.	WSC	2007	DBLP DOI BibTeX RDF
25	Wei-Hua Xu 0003, Wen-Xiu Zhang	A Novel Algorithm of Matrix Computation for Knowledge Reductions in Inconsistent Ordered Information Systems.	FSKD (3)	2007	DBLP DOI BibTeX RDF
25	Dan Gutfreund, Amnon Ta-Shma	Worst-Case to Average-Case Reductions Revisited.	APPROX-RANDOM	2007	DBLP DOI BibTeX RDF
25	Ryan C. Harkins, John M. Hitchcock, Aduri Pavan	Strong Reductions and Isomorphism of Complete Sets.	FSTTCS	2007	DBLP DOI BibTeX RDF
25	Gautam Gupta, Sanjay V. Rajopadhye	Simplifying reductions.	POPL	2006	DBLP DOI BibTeX RDF	equational programming, program transformation, incremental computation, loop optimization, polyhedral model
25	Eli Gafni	Read-Write Reductions.	ICDCN	2006	DBLP DOI BibTeX RDF
25	Srinivas Neginhal, Suraj Kothari	Event Views and Graph Reductions for Understanding System Level C Code.	ICSM	2006	DBLP DOI BibTeX RDF
25	Kiminori Matsuzaki, Zhenjiang Hu, Masato Takeichi	Towards automatic parallelization of tree reductions in dynamic programming.	SPAA	2006	DBLP DOI BibTeX RDF	commutative semiring, parallel tree contraction, parallel programming, dynamic programming, code generator, tree
25	Sami Evangelista, Serge Haddad, Jean-François Pradat-Peyre	Syntactical Colored Petri Nets Reductions.	ATVA	2005	DBLP DOI BibTeX RDF
25	Matthew B. Dwyer, John Hatcliff, Robby, Venkatesh Prasad Ranganath	Exploiting Object Escape and Locking Information in Partial-Order Reductions for Concurrent Object-Oriented Programs.	Formal Methods Syst. Des.	2004	DBLP DOI BibTeX RDF	software verifcation, locking discipline, software model checking, partial order reduction, escape analysis
25	Lucian Ilie, Gonzalo Navarro 0001, Sheng Yu 0001	On NFA Reductions.	Theory Is Forever	2004	DBLP DOI BibTeX RDF